// https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

// 算法思路总结：
// 1. 动态规划求解最长有效括号子串
// 2. 状态定义：dp[i]表示以s[i]结尾的最长有效括号长度
// 3. 状态转移：根据')'前字符分情况处理，考虑嵌套和连接情况
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

class Solution 
{
public:
    int longestValidParentheses(string s) 
    {
        int ret = 0;
        int length = s.size();

        vector<int> dp(length, 0);
        for (int i = 1 ; i < length ; i++)
        {
            if (s[i] == '(')
            {
                dp[i] = 0;
            }
            else
            {
                if (s[i - 1] == '(')
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                else
                {
                    if (i - 1 - dp[i - 1] >= 0 && s[i - 1 - dp[i - 1]] == '(')
                    {
                        dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                }
            }
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

int main()
{
    string s1 = "(()", s2 = ")()())";
    Solution sol;

    cout << sol.longestValidParentheses(s1) << endl;
    cout << sol.longestValidParentheses(s2) << endl;

    return 0;
}